package com.wtgroup.demo.面试题.华为OD;

import java.util.HashMap;

/**
 *
 * N 任务, 部署机器. 每个任务需要占用 x 个机器.
 * 求最少需要的机器数
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/31 11:14
 */
public class Q_最大化节省机器资源 {
    public static void main(String[] args) {
        // int[][] inputs = new int[][]{
        //         {2, 3, 1},
        //         {6, 9, 2},
        //         {0, 5, 1}
        // };
        int[][] inputs = new int[][]{
                {3, 9, 2},
                {4, 7, 3}
        };
        int res = D.func(inputs);
        System.out.println(res);
    }

    // 资料里的方法不好理解, 我这个还行
    static class D {
        /*
         开始时间 -> 机器数
         结束时间 -> -机器数
         随着时间推移, 需要的机器数, 新增或减少(有释放的), 过程中最大值就是所求.
         */

        static HashMap<Integer, Integer> startMap = new HashMap<>();
        static HashMap<Integer, Integer> endMap = new HashMap<>();

        // arr[i] 起止时间, 并行度(占用的机器数)
        static int func(int[][] arr) {
            int maxEnd = 0;
            for (int i = 0; i < arr.length; i ++) {
                int[] item = arr[i];
                startMap.put(item[0], item[2]);
                endMap.put(item[1], item[2]);
                maxEnd = Math.max(maxEnd, item[1]);
            }

            int maxUsed = 0;
            int currUsed = 0;
            for (int t = 0; t <= maxEnd; t++) {
                currUsed += startMap.getOrDefault(t, 0) - endMap.getOrDefault(t, 0);
                maxUsed = Math.max(maxUsed, currUsed);
            }

            return maxUsed;
        }

    }
}
